//
// Created by WINDOWS on 2024/1/9.
//
#include "search.h"
#include <iostream>
#include <algorithm>

using namespace std;

// 顺序查找
index_type search(data_type a[], index_type num, data_type key){
    data_type *b = new data_type[num];
    std::copy(a, a + num, b);
    index_type index = num - 1;
    if(b[index]==key)
        return index;
    b[index] = key;
    index_type i=0;
    while(b[i++]!=key);
    delete [] b;
    return i==(index+1)? -1:i-1;
}

// 二分查找（使用递归）
index_type binarySearch(data_type a[], index_type num, data_type key){
    index_type low = 0;
    index_type high = num - 1;
    return binarySearch_(a,low,high,key);
}
index_type binarySearch_(data_type a[], index_type low, index_type high, data_type key){
   if(low>high)
       return -1;
//   else if(low == high){
//       if(a[low] == key)
//           return low;
//       else
//           return -1;
//   }
    index_type mid = low + (low+high)>>1;
   if(a[mid] == key)
       return mid;
   if(a[mid]>key)
       binarySearch_(a,low,(mid-1),key);
   else
       binarySearch_(a,(mid-1),high,key);
}

//二分插值查找（使用递归）
index_type insertSearch(data_type a[], index_type num, data_type key){
    index_type low = 0;
    index_type high = num - 1;
    return insertSearch_(a,low,high,key);
}
index_type insertSearch_(data_type a[], index_type low, index_type high, data_type key){
    if(low < 0)
        return -2;
    if(low>high)
        return -1;
    if(a[low]==a[high]){
        if(a[high]==key)
            return high;
        else
            return -1;
    }
    index_type mid = low + (key - a[low]) / (a[high] - a[low]) * (high - low);
    if(a[mid] == key)
        return mid;
    if(a[mid]>key)
        binarySearch_(a,low,(mid-1),key);
    else
        binarySearch_(a,(mid-1),high,key);
}